Graph alignment, also called graph matching, is the problem of recovering the hidden correspondence between the vertices of two or more graphs from their correlated edges. In the standard random model, each graph retains every edge of a common Erdős–Rényi graph independently with some probability, and the vertices of each graph are relabeled by an unknown, uniformly random permutation. The problem is thus an average-case, noisy version of graph isomorphism, with applications to de-anonymizing social networks and object tracking in computer vision. Finding the best alignment of two arbitrary graphs is an instance of the quadratic assignment problem, which is NP-hard in the worst case. For two random graphs, however, the past decade has produced sharp information-theoretic thresholds for recovering the alignment and for detecting whether the graphs are correlated at all, as well as polynomial-time algorithms that succeed at constant correlation.
This talk focuses on what changes when more than two graphs are observed. For m correlated graphs, we determine sharp thresholds for exact recovery of all correspondences, and identify a regime in which no pair of graphs can be aligned on its own but all m graphs can be aligned jointly. For the Gaussian analog of this problem, we characterize the detection threshold. I will close with recent progress on polynomial-time algorithms and open problems on whether efficient methods can benefit from additional graphs.
Based on joint work with Bruce Hajek.